
<!DOCTYPE html>
<html>

	<head>
	<title>CAIJL's Blog</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">

	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>

	<link rel="stylesheet" href="/css/bootstrap-slider.min.css">
	<script src="/js/bootstrap-slider.min.js"></script>
	
	<link rel="stylesheet" href="/css/main.css">
	<script src="/js/main.js"></script>
	
	<link rel="stylesheet" href="/css/cursor.css">
	<script src="/js/cursor.js"></script>
	
	
	<link rel="stylesheet" href="/css/code.css">
	<!--link rel="stylesheet" href="/css/markdown.css"-->
	
	<link rel="stylesheet" href="/css/head.css">

	<script src="/js/window.js"></script>
	<script src='//unpkg.com/valine/dist/Valine.min.js'></script>
	</head>
<body>

	<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
	<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
	<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
	<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
	    onload="renderMathInElement(document.body);"></script>
	<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>
	<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="/"><span><span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi mathvariant="bold">C</mi><mi mathvariant="bold">A</mi><mi mathvariant="bold">I</mi><mi mathvariant="bold">J</mi><msup><mi mathvariant="bold">L</mi><mo mathvariant="bold" lspace="0em" rspace="0em">′</mo></msup><mi mathvariant="bold">s</mi><mi mathvariant="bold">B</mi><mi mathvariant="bold">L</mi><mi mathvariant="bold">O</mi><mi mathvariant="bold">G</mi></mrow><annotation encoding="application/x-tex">\mathbf{CAIJL'sBLOG}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height: 0.751892em; vertical-align: 0em;"></span><span class="mord"><span class="mord mathbf">C</span><span class="mord mathbf">A</span><span class="mord mathbf">I</span><span class="mord mathbf">J</span><span class="mord"><span class="mord mathbf">L</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height: 0.751892em;"><span class="" style="top: -3.063em; margin-right: 0.05em;"><span class="pstrut" style="height: 2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathbf mtight">′</span></span></span></span></span></span></span></span></span><span class="mord mathbf">s</span><span class="mord mathbf">B</span><span class="mord mathbf">L</span><span class="mord mathbf">O</span><span class="mord mathbf">G</span></span></span></span></span></span></a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav" style="background-color:#fcfcfc">
			<li><a href="/"><i class="menu-item-icon fa fa-fw fa-home"></i>首页</a></li>
			<li><a href="/archives/"><i class="menu-item-icon fa fa-fw fa-archive"></i>文章</a></li>
			<li><a href="/tags/"><i class="menu-item-icon fa fa-fw fa-tags"></i>标签</a></li>
			<li><a href="/settings/"><i class="menu-item-icon fa fa-fw fa-cogs"></i>设置</a></li>
			<!--li><a href="/about/"><i class="menu-item-icon fa fa-fw fa-user"></i>关于</a></li-->
			<li><a href="/games/"><i class="menu-item-icon fa fa-fw fa-gamepad"></i>其它</a></li>
			

		</ul>
	</div>
	</div>
	</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;position: relative;">
                <img src='/img/bg/52.png' style="width:100%"/>
				<span style="position: absolute;left:15px;bottom:15px;width:90%;"><font class="view-text" style="color:#fcfcfc;font-size:25px">群论入门</font><br><a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/群论/" class="tag"><span  style="background-color: rgb(231, 76, 60);">群论</span></a>&nbsp;<a href="/tags/笔记/" class="tag"><span  style="background-color: rgb(82, 196, 26);">笔记</span></a></span>
			</div>
			<div class="panel panel-default card" style="padding: 10px;" id="main">
                <p>在 <a href="https://www.luogu.com.cn/blog/CJL/conut-ru-men">数数入门</a> 也 copy 了一份，不过有点卡，所以单独开一篇</p>
<!--more-->
<h1 id="_1">群</h1>
<h2 id="_2">定义</h2>
<p>定义集合 <script type="math/tex">G</script> 和二元运算 <script type="math/tex">\times</script> ，记为 <script type="math/tex">(G,\times)</script>，满足以下条件的称为群：
1. 封闭性：<script type="math/tex">\forall a,b\in G,a\times b\in G</script>
2. 结合律：<script type="math/tex">\forall a,b,c\in G,(a\times b)\times c=a\times(b\times c)</script>
3. 单位元（幺元）：<script type="math/tex">\exists e\in G,\forall a\in G,a\times e=e\times a=a</script>
4. 逆元：<script type="math/tex">\forall a\in G,\exists a^\prime\in G,a\times a^\prime=a^\prime\times a=e</script>，不难证明逆元唯一</p>
<h2 id="_3">子群</h2>
<p>若 <script type="math/tex">H</script> 为 <script type="math/tex">G</script> 的一个子集，且 <script type="math/tex">(H,\times)</script> 构成一个群，那么称 <script type="math/tex">H</script> 为 <script type="math/tex">G</script> 的一个子群，记作 <script type="math/tex">H\leq G</script>
</p>
<p>如果 <script type="math/tex">g\in G</script>
- <script type="math/tex">gH=g\times h,h\in H</script> ,那么称其为 <script type="math/tex">H</script> 在 <script type="math/tex">G</script> 内关于 <script type="math/tex">g</script> 的左陪集。
- <script type="math/tex">Hg=h\times g,g\in H</script> ,那么称其为 <script type="math/tex">H</script> 在 <script type="math/tex">G</script> 内关于 <script type="math/tex">g</script> 的右陪集。</p>
<p>陪集的性质（以右陪集为例）：
1. <script type="math/tex">\forall g\in G,|H|=|Hg|</script>
</p>
<p>证明：因为逆元唯一，如果 <script type="math/tex">h_1\not=h_2</script> ，而且 <script type="math/tex">h_1\times g=p=h_2\times g</script> ，那么 <script type="math/tex">h2=p\times g^\prime=h_1</script> ，矛盾，因此 <script type="math/tex">h_1\times g\not=h_2\times g</script>
</p>
<ol>
<li>
<script type="math/tex">\forall g\in G,g\in Hg</script>
</li>
</ol>
<p>证明：<script type="math/tex">H</script> 是群，<script type="math/tex">H</script> 内一定存在一个单位元 <script type="math/tex">e</script> 满足 <script type="math/tex">e\times g=g</script> ，因此 <script type="math/tex">e\times g\in Hg\Leftrightarrow g\in Hg</script>
</p>
<ol>
<li>
<script type="math/tex">Hg=H\Leftrightarrow g\in H</script>
</li>
</ol>
<p>证明：假设 <script type="math/tex">g\not\in H</script> ，<script type="math/tex">eg\not\in Hg</script>，矛盾</p>
<ol>
<li>
<script type="math/tex">Ha=Hb\Leftrightarrow a\times b^{-1}\in H</script>
</li>
</ol>
<p>证明：由性质 <script type="math/tex">3</script> 可得</p>
<ol>
<li>
<script type="math/tex">Ha\cap Hb\not=\varnothing\Leftrightarrow Ha=Hb</script>
</li>
</ol>
<p>证明：假设 <script type="math/tex">c\in Ha,c\in Hb</script>，<script type="math/tex">\exists h_1,h_2</script> 满足 <script type="math/tex">h_1\times a=c,h_2\times b=c,a\times b^{-1}=h_1\times h_2^{-1}\in H</script> ，用性质 <script type="math/tex">4</script> 可以得到。</p>
<ol>
<li>
<script type="math/tex">H</script> 的全体右陪集的并为 <script type="math/tex">G</script>
</li>
</ol>
<p>证明：因为 <script type="math/tex">H</script> 存在单位元 <script type="math/tex">e</script>，<script type="math/tex">g</script> 取遍 <script type="math/tex">G</script> 中的每个元素。</p>
<h2 id="_4">一些表述</h2>
<p>如果 <script type="math/tex">H\le G</script> ：</p>
<p>
<script type="math/tex">H/G</script> 表示 <script type="math/tex">H</script> 的所有左陪集 <script type="math/tex">\{gH|g\in G\}</script>
</p>
<p>
<script type="math/tex">[G:H]</script> 表示 <script type="math/tex">G</script> 中 <script type="math/tex">H</script> 的不同陪集的数量。</p>
<h2 id="_5">拉格朗日定理</h2>
<p><strong>拉格朗日定理</strong>：对于有限群 <script type="math/tex">G</script> 与有限群 <script type="math/tex">H</script>，若 <script type="math/tex">H</script> 为 <script type="math/tex">G</script> 的子群，那么有： <script type="math/tex">|H|\text{整除}|G|</script>
</p>
<p>即 <script type="math/tex">H</script> 的阶整除 <script type="math/tex">G</script> 的阶。</p>
<p>更具体点：<script type="math/tex">|H|\times [G:H]=|G|</script>
</p>
<p>证明：陪集大小和为 <script type="math/tex">|G|</script> ，陪集大小为 <script type="math/tex">|H|</script>，那么 <script type="math/tex">[G:H]=\frac{|G|}{|H|}</script>
</p>
<h2 id="_6">置换群</h2>
<p>设 <script type="math/tex">N=\{1,2,\ldots,n\}</script>，令 <script type="math/tex">M</script> 为 <script type="math/tex">N</script> 的一个排列（一个置换），然后定义两个置换 <script type="math/tex">A</script> 与 <script type="math/tex">B</script> 的 <script type="math/tex">\times</script> 操作得到一个新的置换 <script type="math/tex">C</script> 满足 <script type="math/tex">C_i=B_{A_i}</script>，让集合群 <script type="math/tex">G=(M,\times)</script>。</p>
<p><strong>循环</strong>：置换  <script type="math/tex">
<script type="math/tex; mode=display">\begin{pmatrix}a_1&a_2&\ldots&a_{n-1}&a_n\\ a_2&a_3&\ldots&a_n&a_1\end{pmatrix}</script>
</script> 称为 <script type="math/tex">n</script> 阶循环，记为 <script type="math/tex">(a_1\ a_2\ \ldots\ a_{n-1}\ a_n)</script>。不难发现任何一个置换都可以写作几个循环的乘积，并且结果唯一。</p>
<p><strong>「群作用」</strong>：对于一个集合 <script type="math/tex">M</script> 和群 <script type="math/tex">G</script>，若给定了一个二元函数 <script type="math/tex">\varphi(v,k)</script> 其中 <script type="math/tex">v</script> 为群中的元素，<script type="math/tex">k</script> 为集合元素，且有 <script type="math/tex">\varphi(e,k)=k</script>，<script type="math/tex">\varphi(g,\varphi(s,k))=\varphi(g\times s,k)</script> ，则称群 <script type="math/tex">G</script> 作用与 <script type="math/tex">M</script>
</p>
<h2 id="-">轨道-稳定子定理</h2>
<p><strong>轨道</strong>：作用在 <script type="math/tex">X</script> 上的置换群 <script type="math/tex">G</script>。<script type="math/tex">X</script> 中的元素 <script type="math/tex">x</script> 的 轨道 是在群 <script type="math/tex">G</script> 的作用下能够转移到的元素集合。<script type="math/tex">x</script> 的轨道被记为 <script type="math/tex">G(x)</script>，<script type="math/tex">g(x)</script> 表示群 <script type="math/tex">G</script> 元素 <script type="math/tex">g</script> 作用于 <script type="math/tex">x</script> 的群作用的返回值，即 <script type="math/tex">g(x)=\varphi(g,x)</script>。</p>
<p><strong>稳定子</strong>：<script type="math/tex">G^x=\{g|g(x)=x,g\in G\}</script>
</p>
<p><strong>轨道-稳定子定理</strong>：<script type="math/tex">|G^x||G(x)|=|G|</script>
</p>
<p>证明：由拉格朗日定理可以得出 <script type="math/tex">|G^x|[G:G^x]=|G|</script>，因此只需要证明 <script type="math/tex">[G:G^x]=|G(x)|</script>
</p>
<p>如果 <script type="math/tex">f(x)=g(x)</script>，那么 <script type="math/tex">f(x)g(x)^{-1}=e(x)\in G^x</script>。由于陪集的性质 <script type="math/tex">fG^x=gG^x</script>。因此 <script type="math/tex">fGx=gG^x\Leftrightarrow f=g</script>。</p>
<p>于是让 <script type="math/tex">gG^x</script> 对应 <script type="math/tex">g</script> 就可以不重不漏地表示所有陪集。</p>
<h2 id="rm-burnside">
<script type="math/tex">\rm Burnside</script> 引理</h2>
<p><strong>公式</strong>：定义 <script type="math/tex">G</script> 为一个作用于 <script type="math/tex">X</script> 置换群，如果 <script type="math/tex">x,y\in X</script> 在 <script type="math/tex">G</script> 的作用下可以相等即存在 <script type="math/tex">f\in G</script> 使得 <script type="math/tex">f(x)=y</script> 则定义 <script type="math/tex">x,y</script> 属于一个等价类，则不同的等价类数量为：</p>
<p>
<script type="math/tex; mode=display">|X/G|=\frac1{|G|}\sum_{g\in G}X^g</script>
</p>
<p>其中 <script type="math/tex">X^g</script> 为 <script type="math/tex">X</script> 在 <script type="math/tex">g</script> 的作用下的不动点数量，即满足 <script type="math/tex">g(x)=x</script> 的 <script type="math/tex">x</script> 的数量。</p>
<p>由于每个元素属于仅属于一个轨道，轨道内部在群 <script type="math/tex">G</script> 作用下互达，所以我们可以得到：</p>
<p>
<script type="math/tex; mode=display">|X/G|=\sum_{x\in X}\frac1{[G:G^x]}</script>
</p>
<p>根据轨道-稳定子定理，得到：</p>
<p>
<script type="math/tex; mode=display">[G:G^x]=\frac G{|G^x|}</script>
</p>
<p>
<script type="math/tex; mode=display">|X/G|=\sum_{x/in X}\frac{G^x}{G}</script>
</p>
<p>
<script type="math/tex; mode=display">|X/G|=\frac1{|G|}\sum_{x\in X}G^x</script>
</p>
<p>反过来，就是对于每一个群作用 <script type="math/tex">g</script> ，其作用下不动点的数量。</p>
<h2 id="rm-polya">
<script type="math/tex">\rm Pólya</script> 定理</h2>
<p>对于一个置换 <script type="math/tex">(a_1,a_2,\ldots,a_n)</script>。</p>
<p>在使用 <script type="math/tex">\rm Burnside</script> 解决染色问题的时候，我们需要求的是不动点的数量，而对于上述的置换，假设我们令每个 <script type="math/tex">i</script> 向 <script type="math/tex">a_i</script> 连一条边容易发现会得到若干个环，仔细思考，每个环的颜色应当相同。</p>
<p>我们定义这个环的数量为 <script type="math/tex">c(g)</script> 即置换 <script type="math/tex">g</script> 的轮换(环)数。</p>
<p>那么我们现在可以改写 <script type="math/tex">\rm Burnside</script> 定理为：</p>
<p>
<script type="math/tex; mode=display">\frac1{|G|}\sum_{g\in G}m^{c(g)}</script>
</p>
<h2 id="_7">一些例题</h2>
<h3 id="1p4980-polya">例题1：<a href="https://www.luogu.com.cn/problem/P4980">P4980 【模板】Pólya 定理</a></h3>
<p>考虑置换群 <script type="math/tex">G</script>，有顺时针旋转 <script type="math/tex">0,1,\ldots,n-1</script>。旋转 <script type="math/tex">i</script> 格轮换为 <script type="math/tex">\gcd(i,n)</script>，先给一个比较丑的证明：</p>
<p>假设一个点在 <script type="math/tex">p</script>，旋转 <script type="math/tex">k</script> 次，每次 <script type="math/tex">x</script> 格后回到原点，有：
<script type="math/tex; mode=display">
\begin{aligned}
&p+kx\equiv p\pmod n\Rightarrow kx\equiv 0\pmod n\\
&x|kx\quad \&\quad n|kx\Rightarrow kx=\operatorname{lcm}(x,n)=\frac{nx}{\gcd(n,x)}\\
&\large k=\frac{n}{\gcd(n,x)}
\end{aligned}
</script>
一共有 <script type="math/tex">n</script> 个数，每 <script type="math/tex">\frac n{\gcd(n,x)}</script> 个数构成一个环，共 <script type="math/tex">\gcd(n,x)</script> 个环。</p>
<p>于是直接上 <script type="math/tex">\rm Pólya</script> 定理
<script type="math/tex; mode=display">
\begin{aligned}
&\frac1n\sum_{i=1}^nn^{\gcd(i,n)}\\
&=\frac1n\sum_{d=1}^nn^d\sum_{i=1}^n[gcd(i,n)==d]\\
&=\frac1n\sum_{d|n}n^d\sum_{i=1}^{\frac nd}[\gcd(i,\frac nd)==1]\\
&=\frac1n\sum_{d|n}n^d\varphi(\frac nd)
\end{aligned}
</script>
</p>
<h3 id="2p2561-ahoi2002">例题2：<a href="https://www.luogu.com.cn/problem/P2561">P2561 [AHOI2002]黑白瓷砖</a></h3>
<p>设点的总数为 <script type="math/tex">N=\frac{n\times(n+1)}{2}</script>
</p>
<p>考虑置换群 <script type="math/tex">G</script>:
1. 不动，显然轮换数为 <script type="math/tex">N</script>
2. 旋转 <script type="math/tex">120\degree,240\degree</script>，轮换数为 <script type="math/tex">\lceil\frac N3\rceil</script>
3. 沿三条对称轴翻转，对称轴上有 <script type="math/tex">\lceil\frac n2\rceil</script> 个点，轮换数为 <script type="math/tex">\frac{N-\lceil\frac n2\rceil}{2}+\lceil\frac n2\rceil</script>
</p>
<p>于是得出答案：</p>
<p>
<script type="math/tex; mode=display">\frac16(2^N+2\times2^{\lceil\frac N3\rceil}+3\times2^{(\frac{N-\lceil\frac n 2\rceil} 2+\lceil\frac n2\rceil)})</script>
</p>
<h3 id="3sp419-transp-transposing-is-fun">例题3：<a href="https://www.luogu.com.cn/problem/SP419">SP419 TRANSP - Transposing is Fun</a></h3>
<p>如果一个数为 <script type="math/tex">\overbrace{X}^a\overbrace{Y}^b</script>，那么他将和 <script type="math/tex">\overbrace{Y}^b\overbrace{X}^a</script> 交换位置。朴素地交换是 <script type="math/tex">2^{a+b}</script> 的，是什么让它少了？举个简单的例子：<script type="math/tex">a=2,b=1</script>
<script type="math/tex; mode=display">\begin{pmatrix}
0&1\\
2&3\\
4&5\\
6&7
\end{pmatrix}\Rightarrow 
\begin{pmatrix}
0&4\\
1&5\\
2&6\\
3&7
\end{pmatrix}</script>
写出置换：
<script type="math/tex; mode=display">\begin{pmatrix}
0&1&2&3&5&6&7\\
0&2&1&5&6&5&7
\end{pmatrix}=(0)(12)(356)(7)</script>
每个循环内交换。设循环大小为 <script type="math/tex">x</script>，那么只需交换 <script type="math/tex">x-1</script> 次。若最终由 <script type="math/tex">K</script> 个循环，就少交换 <script type="math/tex">K</script> 次，答案为 <script type="math/tex">2^{a+b}-K</script>
</p>
<p>只需求出多少个循环即可。一个循环内的数有什么特点。由一开始的定义，他们都可以通过多次循环左移 <script type="math/tex">a</script> 位得到。（叫循环左移是因为要把高 <script type="math/tex">a</script> 位移到最低位）。</p>
<p>于是转化问题：一个 <script type="math/tex">a+b</script> 个珠子的环，可以染两种颜色。两个环通过若干次顺时针旋转 <script type="math/tex">a</script> 格得到的称为等价类。问有多少个等价类。等价类的数量就等于上面说的循环个数。</p>
<p>不过这个转 <script type="math/tex">a</script> 格与我们上面的问题略有不同。显然会有 <script type="math/tex">\gcd(a,a+b)=\gcd(a,b)</script> 个循环节，每个循环节互不影响。于是再转化：有 <script type="math/tex">\frac{a+b}{\gcd(a,b)}</script> 个大珠子，每个大珠子有 <script type="math/tex">2^{\gcd(a,b)}</script> 种染色方案。两个环若干次旋转一格能够相等称为同构，求数量。</p>
<p><img alt="抽象图1" src="https://cdn.luogu.com.cn/upload/image_hosting/8lsg4bk5.png">
<img alt="抽象图2" src="https://cdn.luogu.com.cn/upload/image_hosting/ekkyvjgm.png"></p>
<p>直接上 <script type="math/tex">\rm Pólya</script> 即可，推导与上面类似，设 <script type="math/tex">n=\frac{a+b}{\gcd(a,b)}</script>直接给出最终答案：
<script type="math/tex; mode=display">2^{a+b}-\frac{1}{n}\sum_{d|n}2^{gcd(a,b)\times d}\times\varphi(\frac nd)</script>
</p>
<p><a href="https://www.luogu.com.cn/problem/SP422">SP422 TRANSP2 - Transposing is Even More Fun</a> 用类似的方法也能过。</p>
<h3 id="4p4128-shoi2006">例题4：<a href="https://www.luogu.com.cn/problem/P4128">P4128 [SHOI2006] 有色图</a></h3>
<p><del>说好的有色图呢</del></p>
<p>设颜色数量为 <script type="math/tex">k</script>
</p>
<p>我们前面都是点置换，现在变成了边置换。</p>
<p>点置换的数量是 <script type="math/tex">n!</script> 显然不可以直接枚举。考虑一个数列 <script type="math/tex">a_1,a_2,\ldots,a_m</script> 满足 <script type="math/tex">\sum\limits_{i}a_i=n</script> 且 <script type="math/tex">a_i≥a_{i-1}</script>，其中 <script type="math/tex">a_i</script> 表示第 <script type="math/tex">i</script> 个循环节的大小，那么一个数列 <script type="math/tex">a_i</script> 与对应着若干点置换。</p>
<p>更具体的，若 <script type="math/tex">cnt_x</script> 表示 <script type="math/tex">a_i=x</script> 的数量，这个数列对应 <script type="math/tex">\displaystyle\frac{n!}{\prod_ia_i\prod cnt_x}</script> 个点置换。他们边置换的轮换数都是一样的。</p>
<ul>
<li>这条边在循环内部</li>
</ul>
<p>那么每个循环贡献的不动点数量为 <script type="math/tex">\lfloor \dfrac {a_i} 2 \rfloor</script>
</p>
<ul>
<li>这条边在两个循环之间</li>
</ul>
<p>两个循环贡献的不动点数量为 <script type="math/tex">\gcd(a_i,a_j)</script>
</p>
<p>最后对答案的贡献为：</p>
<p>
<script type="math/tex; mode=display">\frac{1}{|G|}\times\dfrac{n!}{\prod a_i \prod \dfrac{x}{cnt_x}}k^{\sum_{i=1}^m\lfloor \frac {a_i} 2 \rfloor+\sum_{1\le i<j\le m} \gcd(a_i,a_j)}</script>
</p>
<p>我们知道 <script type="math/tex">|G|=n!</script>，于是还可以消掉一些东西。</p>
<p>数列 <script type="math/tex">a</script> 的数量不会很大，具体可以参见 <a href="https://oeis.org/A296010">OEIS</a></p>
<p><a href="https://www.luogu.com.cn/problem/P4727">P4727 [HNOI2009]图的同构计数</a> 就是 <script type="math/tex">k=2</script> 的情况</p>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;" href="\article\P5748.html"><i class="fa fa-angle-double-left"></i></a><a style="float: right;" href="\article\P3711.html"><i class="fa fa-angle-double-right"></i></a>
			</div>
			<div class="panel panel-default card" style="padding: 10px;font-size: 20px;" id="vcomments">
				
			</div>
			<script>
				new Valine({
					el: '#vcomments',
					appId: 'PAlFUPg0pQVTFTEo8gCB4BCf-gzGzoHsz',
					appKey: 'U38ejnLUiizJ6vLyp6ql4hRq',
					path: window.location.pathname
				})
			</script>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
                <div style="margin: 10px;">
                    <div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">标题</span>
    <span><font style="font-weight: bold">群论入门</font></span>
	</div><div style="margin-top: 8px;display: flex;"> 
    <span style="flex: 1 0 auto;margin-right: 6px;">日期</span>
    <span>2021-03-02 20:51:00</span>
	</div>
                </div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
					<a href="/tags/2021/" class="tag"><span  style="background-color: rgb(52, 152, 219);">2021</span></a>&nbsp;<a href="/tags/群论/" class="tag"><span  style="background-color: rgb(231, 76, 60);">群论</span></a>&nbsp;<a href="/tags/笔记/" class="tag"><span  style="background-color: rgb(82, 196, 26);">笔记</span></a>
				</div>
				</div>
				
			<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: gray ">312</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/">Settings</a></li>
							<li><a href="/archives/">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div style="height:50px;width:50px"><img src="/img/avatar.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color:gray">caijicjl</a></div>
					</div>
				</div>
		<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-external-link"></i>&emsp;
						<strong>画中画</strong>
					</h3>
				</div>
				<div style="width:100%;margin:10px">
				<input type="text" id="url"/>
				<input value="创建" type="button" onclick="creat('kk')" /> 
				</div>
		</div>
		<script src="/js/hitokoto.js"></script>
							

				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/js/make_toc.js"></script>
				</div>
		</div>
	</div>
 </div>
</body>
</html>
